1. Field of the Invention
This invention relates generally to a task scheduler for use in a multitasking, multiprocessor system, especially one used to perform parallel database queries or other parallel operations. More particularly, the invention relates to the real-time scheduling of jobs composed of multiple independent tasks in a system of tightly-coupled processor complexes in such a way that the tasks within jobs tend to be load balanced, job priorities are respected, and no job is unduly starved for processing time.
2. Description of the Related Art
The response time of a complex query consisting of multiple tasks is determined by the completion time of the last task within that query. The problem is to schedule in real time multiple such queries consisting of independent tasks, employing a load-balancing algorithm to minimize the response times of individual queries, while at the same time respecting external query priorities and avoiding undue starvation of any of the queries in the system.
An environment consisting of a plurality of tightly coupled central processor complexes (CPCs), or central electronic complexes (CECs), is assumed. In such an environment, reassignment of a task is not possible once it is scheduled on a particular complex. It is assumed that tasks have estimated execution times, but that these estimates may be less than perfect. It is also assumed that the individual task execution times may be affected by the selection of the complexes to which they are assigned, and by the time periods in which they are active. However, it is assumed that such effects are known only qualitatively, not quantitatively. For queries in which the completion of an initial task is known to be of value to the user, it is endeavored to complete that task at an early opportunity. (An example might be that task which would return the first tuple to the user, if this can be identified.)